题解 P2451 [SDOI2005]遗传代码

发表于 | 更新于

题意:给定$n$ 个数对$(l,r)$，求一个最短的序列$a$，使得对于所有给定的$(l,r)$ 都存在$i$使得$a_i=l$且 $a_{i+1}=r$。输出这个序列的长度。

想法题，如果一个$l$等于一个$r$，那么他们可以抵消成一个，但是洛谷数据好像有锅，当前位置上的$r>l$时，$ans$加上$r-l$，或者当前位置上的$l<r$时，$ans$加上$l-r$，都是对的。(但洛谷上只有$r-l$是对的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#define ll long long
#define sqr(x) ((x)*(x))
using namespace std;
inline void write(int x) {if (x<0) putchar('-'),x=-x;if (x>=10) write(x/10);putchar(x%10|'0');}
inline void wln(int x) {write(x);puts("");}
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int ans,l[300000],r[300000];
int main(){
    int n=read();
    for (int i=1;i<=n;++i){
        ++l[read()];
        ++r[read()];
    }
    for (int i=1;i<=1000;++i)
        if (r[i]>l[i])
            ans+=abs(r[i]-l[i]);
    cout<<ans+n;
    return 0;
}